// 糖果甜度不一样，划分使得每一段甜度和的最大值最小
#include <iostream>
#include <vector>
using namespace std;
int getAns(vector<int> sweet, int k) {
    int n = sweet.size();
    if(k > n) {
//        k = n;
        return *min_element(sweet.begin(), sweet.end());
    }
//    vector<vector<int>> rec(k, vector<int>(n + 1));
    vector<vector<int>> rec(k + 1, vector<int>(n + 1, INT_MAX));
    for (int i = 0; i < k + 1; ++i) {
        rec[i][0] = 0;
    }
    for (int t = 1; t < k + 1; ++t) {
        for (int i = 1; i < n + 1; ++i) {
            int sum = 0;
            for (int j = i; j >= 0; --j) {
//                if (j != 0) sum += sweet[j - 1];
                rec[t][i] = min(rec[t][i], max(rec[t - 1][j], sum));
                if (j != 0) sum += sweet[j - 1];
            }
        }
    }
    return rec[k][n];
}
int main () {
//    切分k份，前i份的甜度和最大值的最小值
//    f[k][i] = min{j=0,...,i}{max(f[k - 1][j], a[j] +...+ a[i - 1])}
    vector<int> sweet = {2, 3, 4, 1, 6, 2, 3};
    int k = 3;
    cout << getAns(sweet, k) << endl;
    return 0;
}



